package collisions 
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import flash.display.Sprite;
	import flash.utils.ByteArray;
	import flash.utils.Dictionary;
	/**
	 * ...
	 * @author Gareth Williams
	 */
	public final class QuadTree extends Rectangle
	{
		public static var LEAFS:Dictionary = new Dictionary(true);
		public static var NODES:Dictionary = new Dictionary(true);
		
		public const children:LinkedList = new LinkedList(null);
		
		public var count:int = 0;
		public var parent:QuadTree = null;
	
		private var northWest:QuadTree  = null;
		private var northEast:QuadTree = null;
		private var southWest:QuadTree  = null;
		private var southEast:QuadTree = null;
		
		public function QuadTree(x:Number, y:Number, width:Number, height:Number, parent:QuadTree = null)
		{
			super(x, y, width, height);
			this.parent = parent;
		}
		public function destructor():void
		{
			//clear all references held
			var iterator:LinkedList = children;
			while (iterator.next)
			{
				iterator.object = null;
				iterator = iterator.next;
			}
			children.next = null;
			northWest = null;
			northEast = null;
			southWest = null;
			southEast = null;
			parent = null;
			count = 0;
		}
		public function addChild(child:Body):void 
		{
			if (width * height < Constants.MINIMUM_QUADTREE_AREA) return; //granularity bale out
			
			const HALF_WIDTH:Number  = this.width  * 0.5;
			const HALF_HEIGHT:Number = this.height * 0.5;
			
			var childLeft:Number  	= child.x;
			var childRight:Number 	= child.x + child.radius;
			var childTop:Number 	= child.y;
			var childBtm:Number 	= child.y + child.radius;
			
			//beware! here be dragons...recursive dragons.
			//clockwise
			if (childLeft >= left && childRight < left + HALF_WIDTH &&
				childTop >= top  && childBtm < top + HALF_HEIGHT)
			{
				//if (northWest === null) northWest = new QuadTree(left, top, HALF_WIDTH, HALF_HEIGHT, this);
				
				if (northWest === null)
				{
					northWest = QuadTreePool.checkOut(left, top, HALF_WIDTH, HALF_HEIGHT, this);
					NODES[northWest] = true;
				}
				northWest.addChild(child);
			}
			if (childLeft >= left + HALF_WIDTH && childRight < right &&
				childTop >= top  && childBtm < top + HALF_HEIGHT)
			{
				//if (northEast === null) northEast = new QuadTree(left + HALF_WIDTH, top, HALF_WIDTH, HALF_HEIGHT, this);
				
				if (northEast === null)
				{
					northEast = QuadTreePool.checkOut(left + HALF_WIDTH, top, HALF_WIDTH, HALF_HEIGHT, this);
					NODES[northEast] = true;
				}
				northEast.addChild(child);
			}
			if (childLeft >= left + HALF_WIDTH && childRight < right &&
				childTop >= top + HALF_HEIGHT && childBtm < bottom)
			{
				//if (southEast === null) southEast = new QuadTree(left + HALF_WIDTH, top + HALF_HEIGHT, HALF_WIDTH, HALF_HEIGHT, this);
				
				if (southEast === null)
				{
					southEast = QuadTreePool.checkOut(left + HALF_WIDTH, top + HALF_HEIGHT, HALF_WIDTH, HALF_HEIGHT, this);
					NODES[southEast] = true;
				}
				southEast.addChild(child);
			}
			if (childLeft >= left && childRight < left + HALF_WIDTH &&
				childTop >= top + HALF_HEIGHT && childBtm < bottom)
			{
				//if (southWest === null) southWest = new QuadTree(left, top + HALF_HEIGHT, HALF_WIDTH, HALF_HEIGHT, this);
				
				if (southWest === null)
				{
					southWest = QuadTreePool.checkOut(left, top + HALF_HEIGHT, HALF_WIDTH, HALF_HEIGHT, this);
					NODES[southWest] = true;
				}
				southWest.addChild(child);
			}
			
			//if this child didn't go into a quadtree it's a terminating leaf.
			var allQuadsEmpty:Boolean =
				Boolean(northWest || northEast || southEast || southWest) == false;
				
			if (true == allQuadsEmpty)
			{
				this.children.next = new LinkedList(child);
				LEAFS[this] = ++count;
				return;
			}
		}
	}
}
